ABC297 - F - Minimum Bounding Box 2 - かに

ABC297 - F - Minimum Bounding Box 2

問題

https://atcoder.jp/contests/abc297/tasks/abc297_f

期待値は総和÷すべて場合の数なので、この$ 2つが分かれば解ける

すべての場合の数は$ HWマスから$ Kマス選ぶ場合の数なので、

$ \binom{HW}{K}

主客転倒して、長方形ではなく各マスが何回数えられるかをマスごとに考える。

逆に、あるマス$ hwが数えられないパターンは、選ばれるマスを$ x_1y_1,\dots x_Ky_Kとしたときに

①$ \forall i \; x_i<h

②$ \forall i \; x_i > h

③$ \forall i \; y_i < w

④$ \forall i \; y_i>w

を一つでも満たすもの。この和集合の濃度が分かればよいので、包除原理で解ける。

code: f.py

def cmb(n, r):

"""

mod 上の二項係数 nCr

前処理：O(N)

クエリ：O(1)

"""

if (r < 0) or (n < r):

return 0

return factn * factinvr % mod * factinvn-r % mod

mod = 998244353

# 前処理

Nll = 10 ** 6 + 10 # Nll は必要分だけ用意する

fact = 1, 1 # factn = (n! mod p)

inv = 0, 1 # invn = (n^(-1) mod p)

factinv = 1, 1 # factinvn = ((n!)^(-1) mod p)

for i in range(2, Nll + 1):

fact.append((fact-1 * i) % mod)

inv.append((-invmod % i * (mod // i)) % mod)

factinv.append((factinv-1 * inv-1) % mod)

#####

H, W, K = map(int, input().split())

HW = H * W

ALL = cmb(HW, K)

agg = 0

for i in range(HW):

h, w = divmod(i, W)

h, w = h+1, w+1

inc = 0

for x, y in zip(h-1, H-h, H, H, W, W, w-1, W-w):

inc += cmb(x * y, K)

inc %= mod

exc = 0

for x in h-1, H-h:

for y in w-1, W-w:

exc += cmb(x * y, K)

exc %= mod

agg = (agg + ALL - inc + exc) % mod

print(agg * pow(ALL, mod-2, mod) % mod)